class Solution {
public:
    int tribonacci(int n) {
        //状态表示为T[N]
        vector<int> dp{0,1,1};//填充T[0],T[1],T[2]
        //状态方程为T[N]=T[N-3]+T[N-2]+T[N-1]
        if(n<3){
            return dp[n];
        }
        int i=2;
        while(i<n){
            i++;
            dp.push_back(dp[i-1]+dp[i-2]+dp[i-3]);
        }
        return dp[i];
    }
};